package com.dmall.graph.euler;

import com.dmall.graph.Graph;
import com.dmall.graph.dfs.app.CC;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * 使用回溯法寻找欧拉回路
 * @author: xiao1.wang
 * @date: 2022/7/31 14:29
 */
public class EulerLoopDFS {

    private Graph G;

    public EulerLoopDFS(Graph G) {
        this.G = G;
    }

    public boolean hasEulerLoop() {
        CC cc = new CC(G);
        if (cc.count() > 1) {
            return false;
        }
        for (int v = 0; v < G.V(); v++) {
            if (G.degree(v) % 2 == 1) {
                return false;
            }
        }
        return true;
    }

    public List<Integer> result() {
        List<Integer> res = new ArrayList<>();
        if (!hasEulerLoop()) {
            return res;
        }
        Graph g = (Graph) G.clone();
        int w = g.adj(0).iterator().next();
        res.add(0);
        dfs(w, 0, G.E(), g, res);
        return res;
    }

    private boolean dfs(int v, int parent, int left, Graph g, List<Integer> res) {
        res.add(v);
        left --;
        g.removeEdge(v, parent);
        if (left == 0 && v == 0) {
            // 剩余的边数为0，并且回到起始点，表示每条边都已经走过一次了，找到了一条欧拉回路了
            return true;
        }
        if (g.degree(v) == 0) {
            res.remove(res.size() - 1);
            g.addEdge(v, parent);
            return false;
        }
        Iterable<Integer> adj = g.adj(v);
        Iterator<Integer> iterator = adj.iterator();
        ArrayList<Integer> list = new ArrayList<>();
        while (iterator.hasNext()) {
            list.add(iterator.next());
        }
        for (int w : list) {
            if (dfs(w, v, left, g, res)) {
                return true;
            }
        }
        res.remove(res.size() - 1);
        g.addEdge(v, parent);
        return false;
    }

    public static void main(String[] args) {
        String filename = EulerLoopDFS.class.getClassLoader().getResource("g.txt").getPath();
        Graph g = new Graph(filename);
        EulerLoopDFS el = new EulerLoopDFS(g);
        System.out.println(el.result());

        String filename2 = EulerLoopDFS.class.getClassLoader().getResource("g2.txt").getPath();
        Graph g2 = new Graph(filename2);
        EulerLoopDFS el2 = new EulerLoopDFS(g2);
        System.out.println(el2.result());
    }
}
